home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / atre12.zip / LF.ZIP / SYNAN.Y < prev    next >
Text File  |  1991-07-05  |  19KB  |  723 lines
  1. %{
  2.  
  3. /*****************************************************************************
  4.  ****                                                                     ****
  5.  **** synan.y                                                             ****
  6.  ****                                                                     ****
  7.  **** Copyright (C) A. Dwelly and W.W. Armstrong, 1990.                   ****
  8.  ****                                                                     ****
  9.  **** All rights reserved.                                                ****
  10.  ****                                                                     ****
  11.  **** This is the syntax analyser for the small language `lf` that learns ****
  12.  **** a function using the atree package. Atree is an adaptive            ****
  13.  **** logic network package based on work done by Prof. W. W. Armstrong   ****
  14.  **** and others in the Department of Computing Science, University of    ****
  15.  **** Alberta, and previous work at the Universite de Montreal, and at    ****
  16.  **** AT&T Bell Laboratories, Holmdel, N. J.  The software demonstrates   ****
  17.  **** that networks consisting of many layers of linear threshold         ****
  18.  **** elements can indeed be effectively trained.                         ****
  19.  ****                                                                     ****
  20.  **** License:                                                            ****
  21.  **** A royalty-free license is granted for the use of this software for  ****
  22.  **** NON-COMMERCIAL PURPOSES ONLY. The software may be copied and        ****
  23.  **** modified provided this notice appears in its entirety and unchanged ****
  24.  **** in all copies, whether changed or not.  Persons modifying the code  ****
  25.  **** are requested to state the date, the changes made and who made them ****
  26.  **** in the modification history.                                        ****
  27.  ****                                                                     ****
  28.  **** Warranty:                                                           ****
  29.  **** No warranty of any kind is provided with this software.             ****
  30.  **** This software is not supported.  Neither the authors, nor the       ****
  31.  **** University of Alberta, its officers, agents, servants or employees  ****
  32.  **** shall be liable or responsible in any way for any damage to         ****
  33.  **** property or direct personal or consequential injury of any nature   ****
  34.  **** whatsoever that may be suffered or sustained by any licensee, user  ****
  35.  **** or any other party as a consequence of the use or disposition of    ****
  36.  **** this software.                                                      ****
  37.  ****                                                                     ****
  38.  **** Patent:                                                             ****
  39.  **** The use of a digital circuit which transmits a signal indicating    ****
  40.  **** heuristic responsibility is protected by U. S. Patent 3,934,231     ****
  41.  **** and others assigned to Dendronic Decisions Limited of Edmonton,     ****
  42.  **** W. W. Armstrong, President.                                         ****
  43.  ****                                                                     **** 
  44.  **** A royalty-free license is granted for the use of this patent to     ****
  45.  **** run this software for NON-COMMERCIAL PURPOSES ONLY and the          ****
  46.  **** extension of this patent license to modified versions of this       ****
  47.  **** software is granted provided the purpose is NON-COMMERCIAL ONLY.    ****
  48.  ****                                                                     ****
  49.  **** Modification history:                                               ****
  50.  ****                                                                     ****
  51.  **** 09.02.10 Initial implementation, A.Dwelly                           ****
  52.  **** 91.04.15 Port to PC and minor bug fixes, R. Manderscheid            ****
  53.  **** 91.05.20 Port to Windows, Monroe Thomas                             ****
  54.  ****                                                                     ****
  55.  *****************************************************************************/
  56.  
  57. #include <stdio.h>
  58. #include <stdlib.h>
  59. #include <ctype.h>
  60. #include <windows.h>
  61. #include "atree.h"
  62. #include "lf.h"
  63.  
  64. int line_no;
  65. int in_int;
  66. float in_real;
  67. int tuple_ptr;
  68. int table_ptr;
  69. int tmp_max_sz;
  70. int table_size;
  71. float **tmp_table;
  72. bool train_size_flag;
  73. bool test_size_flag;
  74. bool largest_flag;
  75. bool smallest_flag;
  76. extern prog_type prog;
  77. %}
  78.  
  79. %token FUNCTION
  80. %token DOMAIN
  81. %token DIMENSIONS
  82. %token EQUALS
  83. %token INTEGER
  84. %token QUANTIZATION
  85. %token COLON
  86. %token TRAINING
  87. %token SET
  88. %token SIZE
  89. %token TEST
  90. %token CODING
  91. %token LARGEST
  92. %token SMALLEST
  93. %token REAL
  94. %token TREE
  95. %token MIN
  96. %token MAX 
  97. %token CORRECT
  98. %token EPOCHS
  99. %token VOTE
  100. %token IDENTIFIER
  101.  
  102. %% /* Program definition */
  103.  
  104. program : function_spec tree_spec
  105.         | tree_spec function_spec
  106.     ;
  107.  
  108. function_spec : FUNCTION dimension function_statements
  109.  
  110. dimension : DOMAIN DIMENSIONS EQUALS INTEGER
  111.       {
  112.           /* Temporary */
  113.  
  114.           in_int++;
  115.  
  116.           prog.dimensions = in_int;
  117.           prog.quant = (int *) malloc((unsigned)sizeof(int) * in_int);
  118.           MEMCHECK(prog.quant);
  119.  
  120.           prog.quant_step =
  121.           (float *)malloc((unsigned)sizeof(float) * in_int);
  122.           MEMCHECK(prog.quant_step);
  123.  
  124.               prog.train_table =
  125.           (float **)malloc((unsigned)sizeof(float *) * in_int);
  126.           MEMCHECK(prog.train_table);
  127.  
  128.           prog.test_table =
  129.           (float **)malloc((unsigned)sizeof(float *) * in_int);
  130.           MEMCHECK(prog.test_table);
  131.  
  132.               prog.test_table_quant =
  133.           (int **)malloc((unsigned) sizeof(int *) * in_int);
  134.           MEMCHECK(prog.test_table_quant);
  135.  
  136.               prog.largest =
  137.           (float *)malloc((unsigned)sizeof(float) * in_int);
  138.           MEMCHECK(prog.largest);
  139.  
  140.               prog.smallest =
  141.           (float *)malloc((unsigned)sizeof(float) * in_int);
  142.           MEMCHECK(prog.smallest);
  143.  
  144.           prog.string_width =
  145.           (int *)malloc((unsigned)sizeof(int) * in_int);
  146.           MEMCHECK(prog.string_width);
  147.  
  148.           prog.walk_step = (int *)malloc((unsigned)sizeof(int) * in_int);
  149.           MEMCHECK(prog.walk_step);
  150.  
  151. #pragma warn -sus
  152.  
  153.           prog.random_walk =
  154.           (LPBIT_VEC *)malloc((unsigned)sizeof(LPBIT_VEC) * in_int);
  155.           MEMCHECK(prog.random_walk);
  156.  
  157. #pragma warn .sus
  158.  
  159.           tmp_table = (float **)malloc((unsigned)sizeof(float *) * in_int);
  160.           MEMCHECK(tmp_table);
  161.       }
  162.  
  163. function_statements : function_statement
  164.             | function_statements function_statement
  165.  
  166. function_statement : quantization
  167.            | coding
  168.            | train_table_size
  169.            | train_table
  170.            | test_table_size
  171.            | test_table
  172.            | largest
  173.            | smallest
  174.                ;
  175.  
  176. quantization : QUANTIZATION EQUALS 
  177.              {
  178.          tuple_ptr = 0;
  179.          }
  180.          quant_list 
  181.          {
  182.          if (tuple_ptr > prog.dimensions)
  183.          {
  184.                  prog.error = TRUE;
  185.                  printf("Semantics error : too many elements in quantization list on line %d\n", line_no);
  186.          }
  187.          if (tuple_ptr < prog.dimensions)
  188.          {
  189.                  prog.error = TRUE;
  190.                  printf("Semantics error : not enough elements in quantization list on line %d\n", line_no);
  191.          }
  192.          }
  193.          ;
  194.  
  195. quant_list : INTEGER
  196.          {
  197.          prog.quant[tuple_ptr] = in_int;
  198.          tuple_ptr++;
  199.          }
  200.         | quant_list  INTEGER
  201.              {
  202.          prog.quant[tuple_ptr] = in_int;
  203.          tuple_ptr++;
  204.          }
  205.          ;
  206.  
  207. coding : CODING EQUALS 
  208.        {
  209.        tuple_ptr = 0;
  210.        }
  211.        code_list 
  212.        {
  213.        if (tuple_ptr > prog.dimensions)
  214.        {
  215.            prog.error = TRUE;
  216.            printf("Semantics error : too many elements in coding list on line %d\n", line_no);
  217.        }
  218.        if (tuple_ptr < prog.dimensions)
  219.        {
  220.            prog.error = TRUE;
  221.            printf("Semantics error : not enough elements in coding list on line %d\n", line_no);
  222.        }
  223.        }
  224.        ;
  225.  
  226. code_list : INTEGER 
  227.       {
  228.           prog.string_width[tuple_ptr] = in_int;
  229.       }
  230.       COLON INTEGER
  231.       {
  232.           prog.walk_step[tuple_ptr] = in_int;
  233.           tuple_ptr++;
  234.       }
  235.       | code_list INTEGER 
  236.       {
  237.           prog.string_width[tuple_ptr] = in_int;
  238.       }
  239.       COLON INTEGER
  240.       {
  241.           prog.walk_step[tuple_ptr] = in_int;
  242.           tuple_ptr++;
  243.       }
  244.       ;
  245. train_table_size : TRAINING SET SIZE EQUALS INTEGER
  246.             {
  247.         prog.trainset_sz = in_int;
  248.         train_size_flag = TRUE;
  249.         }
  250.         ;
  251.  
  252. train_table : TRAINING SET EQUALS
  253.             {
  254.         if (!train_size_flag)
  255.         {
  256.             printf("Semantics error : training set defined before size\n");
  257.             exit(1);
  258.         }
  259.         else
  260.         {
  261.             int i;
  262.  
  263.             tmp_max_sz = prog.trainset_sz;
  264.             tuple_ptr = 0;
  265.             table_ptr = 0;
  266.             for (i = 0; i < prog.dimensions; i++)
  267.             {
  268.                 tmp_table[i] = (float *)malloc((unsigned)sizeof(float)*prog.trainset_sz);
  269.             MEMCHECK(tmp_table[i]);
  270.             }
  271.         }
  272.         }
  273.         table
  274.         {
  275.         int i;
  276.  
  277.         if (tuple_ptr < prog.trainset_sz)
  278.         {
  279.             prog.error = TRUE;
  280.                 printf("Semantics error : not enough elements in training set\n");
  281.         }
  282.         for (i = 0; i < prog.dimensions; i++)
  283.         {
  284.             prog.train_table[i] = tmp_table[i];
  285.         }
  286.         }
  287.  
  288. test_table_size : TEST SET SIZE EQUALS INTEGER 
  289.             {
  290.         prog.testset_sz = in_int;
  291.         test_size_flag = TRUE;
  292.         }
  293.         ;
  294.  
  295. test_table  : TEST SET EQUALS
  296.         {
  297.         if (!test_size_flag)
  298.         {
  299.             printf("Semantics error : test set defined before size\n");
  300.             exit(1);
  301.         }
  302.         else
  303.         {
  304.             int i;
  305.  
  306.             tmp_max_sz = prog.testset_sz;
  307.             tuple_ptr = 0;
  308.             table_ptr = 0;
  309.             for (i = 0; i < prog.dimensions; i++)
  310.             {
  311.                 tmp_table[i] = 
  312.                 (float *)malloc((unsigned)sizeof(float) * prog.testset_sz);
  313.             MEMCHECK(tmp_table[i]);
  314.                 prog.test_table_quant[i] = 
  315.                 (int *)malloc((unsigned) sizeof(int) * prog.testset_sz);
  316.             MEMCHECK(prog.test_table_quant[i]);
  317.             }
  318.         }
  319.         }
  320.         table
  321.         {
  322.         int i;
  323.  
  324.             if (tuple_ptr < prog.testset_sz)
  325.         {
  326.             prog.error = TRUE;
  327.                 printf("Semantics error : not enough elements in test set\n");
  328.         }
  329.         for (i = 0; i < prog.dimensions; i++)
  330.         {
  331.             prog.test_table[i] = tmp_table[i];
  332.         }
  333.         }
  334.         ;
  335.  
  336. table : num
  337.       {
  338.       tmp_table[table_ptr][tuple_ptr] = in_real;
  339.       table_ptr++;
  340.       if (table_ptr == prog.dimensions)
  341.       {
  342.           table_ptr = 0;
  343.           tuple_ptr++;
  344.       }
  345.       if (tuple_ptr > tmp_max_sz)
  346.       {
  347.           printf("Semantics error: too many elements in table\n");
  348.           exit(1);
  349.       }
  350.       }
  351.       | table num
  352.       {
  353.       tmp_table[table_ptr][tuple_ptr] = in_real;
  354.       table_ptr++;
  355.       if (table_ptr == prog.dimensions)
  356.       {
  357.           table_ptr = 0;
  358.           tuple_ptr++;
  359.       }
  360.       if (tuple_ptr > tmp_max_sz)
  361.       {
  362.           printf("Semantics error: too many elements in table\n");
  363.           exit(1);
  364.       }
  365.       }
  366.       ;
  367.  
  368. num : REAL
  369.     | INTEGER
  370.     {
  371.     in_real = (float) in_int;
  372.     }
  373.     ;
  374.  
  375. largest : LARGEST EQUALS 
  376.              {
  377.          tuple_ptr = 0;
  378.          largest_flag = TRUE;
  379.          }
  380.          largest_list 
  381.          {
  382.          if (tuple_ptr > prog.dimensions)
  383.          {
  384.                  prog.error = TRUE;
  385.                  printf("Semantics error : too many elements in largest list on line %d\n", line_no);
  386.          }
  387.          if (tuple_ptr < prog.dimensions)
  388.          {
  389.                  prog.error = TRUE;
  390.                  printf("Semantics error : not enough elements in largest list on line %d\n", line_no);
  391.          }
  392.          }
  393.          ;
  394.  
  395. largest_list : num
  396.          {
  397.          prog.largest[tuple_ptr] = in_real;
  398.          tuple_ptr++;
  399.          }
  400.          | largest_list num
  401.              {
  402.          prog.largest[tuple_ptr] = in_real;
  403.          tuple_ptr++;
  404.          }
  405.          ;
  406.  
  407. smallest : SMALLEST EQUALS 
  408.              {
  409.          tuple_ptr = 0;
  410.          smallest_flag = TRUE;
  411.          }
  412.          smallest_list 
  413.          {
  414.          if (tuple_ptr > prog.dimensions)
  415.          {
  416.                  prog.error = TRUE;
  417.                  printf("Semantics error : too many elements in smallest list on line %d\n", line_no);
  418.          }
  419.          if (tuple_ptr < prog.dimensions)
  420.          {
  421.                  prog.error = TRUE;
  422.                  printf("Semantics error : not enough elements in smallest list on line %d\n", line_no);
  423.          }
  424.          }
  425.          ;
  426.  
  427. smallest_list : num
  428.          {
  429.          prog.smallest[tuple_ptr] = in_real;
  430.          tuple_ptr++;
  431.          }
  432.          | smallest_list num 
  433.              {
  434.          prog.smallest[tuple_ptr] = in_real;
  435.          tuple_ptr++;
  436.          }
  437.  
  438. tree_spec : TREE tree_statements
  439.  
  440. tree_statements : tree_statement
  441.         | tree_statements tree_statement
  442.         
  443. tree_statement : tree_size 
  444.            | max_correct
  445.            | max_epochs
  446.            | vote_no
  447.            ;
  448.  
  449. tree_size : SIZE EQUALS INTEGER
  450.           {
  451.           prog.tree_sz = in_int;
  452.       }
  453.       ;
  454.  
  455. max_correct : MIN CORRECT EQUALS INTEGER
  456.             {
  457.         prog.max_correct = in_int;
  458.         }
  459.         ;
  460.  
  461. max_epochs : MAX EPOCHS EQUALS INTEGER
  462.            {
  463.            prog.max_epochs = in_int;
  464.        }
  465.        ;
  466.  
  467. vote_no : VOTE EQUALS INTEGER
  468.     {
  469.         if (in_int % 2 != 1)
  470.         {
  471.                 printf("Semantics error : vote number is even\n");
  472.         exit(1);
  473.         }
  474.         prog.vote = in_int;
  475.     }
  476.     ;
  477. %%
  478.  
  479.  
  480. /* Lexical states */
  481.  
  482. #define LEX_START 0
  483. #define LEX_INT 1
  484. #define LEX_DEC 2
  485. #define LEX_IDENT 3
  486. #define LEX_PUNCT 4
  487. #define LEX_COMMENT 5
  488. #define LEX_STOP 1000
  489.  
  490. #define MAX_LEN_BUF 1000
  491.  
  492. int lexstate;
  493. int nextchar;
  494. FILE *yyin;
  495.  
  496. #define ISCOMMENT(c) (c == '#')
  497.  
  498. void
  499. lexinit()
  500.  
  501. {
  502.     lexstate = LEX_START;
  503.     nextchar = getc(yyin);
  504. }
  505.  
  506. isextdigit(c)
  507.  
  508. char c;
  509.  
  510. { 
  511.     return((c == 'e') || (c == 'E') || (c == '+') || (c == '-') || isdigit(c));
  512. }
  513.  
  514. iswhite(c)
  515.  
  516. char c;
  517.  
  518. {
  519.     if (c == '\n')
  520.     {
  521.     line_no++;
  522.     return(TRUE);
  523.     }
  524.     else
  525.     {
  526.         return((c == 0) || (c == ' ') || (c == '\t'));
  527.     }
  528. }
  529.  
  530. gettoken(str)
  531.  
  532. char *str;
  533.  
  534. {
  535.  
  536.     int i;
  537.     int outcode;
  538.  
  539.     static struct tok
  540.     {
  541.     char *token;
  542.     int code;
  543.     } toktab[] = 
  544.     {
  545.     "function"    , FUNCTION,
  546.     "dimension"   , DIMENSIONS, 
  547.     "dimensions"  , DIMENSIONS, 
  548.     "="           , EQUALS,
  549.     "quantization", QUANTIZATION,
  550.     ":"           , COLON,
  551.     "coding"      , CODING,
  552.     "training"    , TRAINING,
  553.     "set"         , SET,
  554.     "size"        , SIZE,
  555.     "test"        , TEST,
  556.     "tree"        , TREE,
  557.     "minimum"     , MIN,
  558.     "min"         , MIN,
  559.     "maximum"     , MAX,
  560.     "max"         , MAX,
  561.     "correct"     , CORRECT,
  562.     "epochs"      , EPOCHS,
  563.     "largest"     , LARGEST,
  564.     "smallest"    , SMALLEST,
  565.     "domain"      , DOMAIN,
  566.     "vote"        , VOTE,
  567.     NULL          ,0
  568.     };
  569.  
  570.     outcode = IDENTIFIER;
  571.  
  572.     for (i = 0; toktab[i].token != NULL; i++)
  573.     {
  574.     if (strcmp(str,toktab[i].token) == 0)
  575.     {
  576.         outcode = toktab[i].code;
  577.         break;
  578.     }
  579.     }
  580.  
  581.     return(outcode);
  582. }
  583.  
  584. int
  585. yylex()
  586.  
  587. {
  588.     char yytext[MAX_LEN_BUF];
  589.     int bufptr;
  590.     bool found_token;
  591.     int token;
  592.  
  593.     found_token = FALSE;
  594.     bufptr = 0;
  595.  
  596.     while (!found_token)
  597.     {
  598.     switch (lexstate)
  599.     {
  600.         case LEX_START:
  601.         while (iswhite(nextchar))
  602.         {
  603.              nextchar = getc(yyin);
  604.         }
  605.  
  606.         if (ISCOMMENT(nextchar))
  607.         {
  608.             nextchar = getc(yyin);
  609.             lexstate = LEX_COMMENT;
  610.         }
  611.         else if (isdigit(nextchar) || (nextchar == '-'))
  612.         {
  613.             yytext[bufptr++] = nextchar;
  614.             nextchar = getc(yyin);
  615.             lexstate = LEX_INT;
  616.         }
  617.         else if (isalpha(nextchar))
  618.         {
  619.             yytext[bufptr++] = nextchar;
  620.             nextchar = getc(yyin);
  621.             lexstate = LEX_IDENT;
  622.         }
  623.         else if (ispunct(nextchar))
  624.         {
  625.             yytext[bufptr++] = nextchar;
  626.             nextchar = getc(yyin);
  627.             lexstate = LEX_PUNCT;
  628.         }
  629.         else if (nextchar == EOF)
  630.         {
  631.             lexstate = LEX_STOP;
  632.         }
  633.         else
  634.         {
  635.             printf("Lexical error: unrecognized character %d\n",(int) nextchar);
  636.             exit(1);
  637.         }
  638.         break;
  639.  
  640.         case LEX_INT:
  641.         while (isdigit(nextchar))
  642.         {
  643.             yytext[bufptr++] = nextchar;
  644.             nextchar = getc(yyin);
  645.         }
  646.         if (nextchar == '.')
  647.         {
  648.             yytext[bufptr++] = nextchar;
  649.             nextchar = getc(yyin);
  650.             lexstate = LEX_DEC;
  651.         }
  652.         else
  653.         {
  654.             yytext[bufptr] = 0;
  655.             in_int = atoi(yytext);
  656.             token = INTEGER;
  657.             found_token = TRUE;
  658.         }
  659.         break;
  660.  
  661.         case LEX_DEC:
  662.         while (isextdigit(nextchar))
  663.         {
  664.             yytext[bufptr++] = nextchar;
  665.             nextchar = getc(yyin);
  666.         }
  667.         yytext[bufptr] = 0;
  668.         sscanf(yytext,"%g",&in_real);
  669.         token = REAL;
  670.         found_token = TRUE;
  671.         break;
  672.  
  673.         case LEX_IDENT:
  674.         while (isalpha(nextchar) || isdigit(nextchar))
  675.         {
  676.             yytext[bufptr++] = nextchar;
  677.             nextchar = getc(yyin);
  678.         }
  679.         yytext[bufptr] = 0;
  680.         token = gettoken(yytext);
  681.         found_token = TRUE;
  682.         break;
  683.  
  684.         case LEX_PUNCT:
  685.         yytext[bufptr] = 0;
  686.         token = gettoken(yytext);
  687.         found_token = TRUE;
  688.         break;
  689.  
  690.         case LEX_COMMENT:
  691.         while (nextchar != '\n')
  692.         {
  693.             nextchar = getc(yyin);
  694.         }
  695.         lexstate = LEX_START;
  696.         break;
  697.  
  698.         case LEX_STOP:
  699.         token = 0;
  700.         found_token = TRUE;
  701.         break;
  702.     }
  703.     }
  704.  
  705.     if (lexstate != LEX_STOP)
  706.     {
  707.     lexstate = LEX_START;
  708.     }
  709.     return(token);
  710. }
  711.  
  712. #pragma argsused
  713. #pragma warn -rvl
  714.  
  715. yyerror(s)
  716. char *s;
  717. {
  718.     fprintf(stderr,"Error found on line %d\n",line_no);
  719.     prog.error = TRUE;
  720. }
  721.  
  722. #pragma warn .rvl
  723.